#pragma once
#include <vector>

namespace bit
{
	template<size_t N> // N是需要多少⽐特位
	class bitset
	{
	public:
		bitset()
		{
			_bs.resize(N / 32 + 1);
		}

		// x 映射的位标记为 1
		void set(size_t x)
		{ //在第 i 个值的 第 j 位 
			size_t i = x / 32;
			size_t j = x % 32;

			_bs[i] |= (1 << j);
		}

		// x 映射的位标记为 0
		void reset(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

			_bs[i] &= (~(1 << j)); // 让1左移j 位
		}

		// x 映射位为1返回真，0返回假
		bool test(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

			return _bs[i] & (1 << j);
		}


	private:
		std::vector<int>_bs;
	};


	//模拟位图找交集
	void test_bitset()
	{
		int a1[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };
		int a2[] = { 5,3,5,99,6,99,33,66 };

		bitset<100> bs1;
		bitset<100> bs2;

		for (auto e : a1)
		{
			bs1.set(e);
		}

		for (auto e : a2)
		{
			bs2.set(e);
		}

		for (size_t i = 0; i < 100; i++)
		{
			if (bs1.test(i) && bs2.test(i))
			{
				cout << i << endl;
			}
		}
	}


	//模拟 找到出现次数不超过2次的所有整数
	template<size_t N>
	class twobitset
	{
	public:

		void set(size_t x)
		{
			bool bit1 = _bs1.test(x);
			bool bit2 = _bs2.test(x);

			if (!bit1 && !bit2) // 00 -> 01
			{
				_bs2.set(x);
			}

			else if (!bit1 && bit2) // 01 -> 10
			{
				_bs1.set(x);
				_bs2.reset(x);
			}

			else if (bit1 && !bit2) // 10 -> 11
			{
				_bs1.set(x);
				_bs2.set(x);
			}
		}

		// 返回 0 出现 0 次
		// 返回 1 出现 1 次
		// 返回 2 出现 2 次
		// 返回 3 出现 3 次及以上

		int get_count(size_t x) //获取出现次数
		{
			bool bit1 = _bs1.test(x);
			bool bit2 = _bs2.test(x);

			if (!bit1 && !bit2)
			{
				return 0;
			}

			else if (!bit1 && bit2)
			{
				return 1;
			}

			else if (bit1 && !bit2)
			{
				return 2;
			}

			else return 3;
		}
	private:
		bitset<N> _bs1;
		bitset<N> _bs2;
	};
	
	void test_twobitset()
	{
		bit::twobitset<100> tbs;
		int a[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6,6,6,6,7,9 };
		for (auto e : a)
		{
			tbs.set(e);
		}
		for (size_t i = 0; i < 100; ++i)
		{
			cout << i << "->" << tbs.get_count(i) << endl;
			if (tbs.get_count(i) == 1 || tbs.get_count(i) == 2)
			{
				cout << i << endl;
			}
		}
	}

}









namespace qian
{
	// 非类型模板参数
	template <size_t N>
	class bitset
	{
	public:
		bitset() //构造函数
		{
			//_bits.resize(N / 8 + 1, 0);
			//可能开的比特位恰好满足数字的个数，也可能最多浪费7个比特位
			//_bits.resize(N >> 3 + 1, 0);//位运算符优先级过低，这里先进行+运算，则结果和我们预想的不一致，发生错误。
			_bits.resize((N >> 3) + 1, 0);
		}

		void set(size_t x)  // x 映射的位标记为 1
		{
			size_t i = x >> 3; //映射到第几个char中
			size_t j = x % 8; //映射到char中第几个比特位
			//将映射到位图中的比特位置一
			_bits[i] |= 1 << j;
		}

		void reset(size_t x)  // x 映射的位标记为 0
		{
			size_t i = x >> 3;
			size_t j = x % 8;
			_bits[i] &= ~(1 << j);
		}

		bool test(size_t x) // x 映射位为1返回真，0返回假
		{
			size_t i = x / 8;
			size_t j = x % 8;
			return _bits[i] & (1 << j);//这里不是&=，因为test不改变位图，只是判断一下而已
			//有些编译器bool值是四个字节，返回时会发生整型提升，高位补符号位，但这些都不重要，只要是非0就行，判断为真
			//我的编译器bool值是一个字节
		}
	private:
		vector<char> _bits;
	};

	void test_bitset()
	{
		cout << "bool的字节大小:" << sizeof(bool) << endl;

		//qian::bitset<100> bs1;//0-99的整数判断在不在，开范围大小
		qian::bitset<-1> bs2; // 用-1转成无符号数代替无符号数的最大数42亿9千万
		//qian::bitset<0xffffffff> bs2;//，0xffffffff，INT_MAX是21亿，用UINT_MAX
		bs2.set(10);
		bs2.set(4599);
		bs2.set(99999);
		bs2.set(88888);

		cout << bs2.test(10) << endl;
		cout << bs2.test(4599) << endl;
		cout << bs2.test(99) << endl;
		cout << bs2.test(100) << endl;
		cout << bs2.test(101) << endl;
		cout << bs2.test(88888) << endl;

		bs2.reset(4599);
		bs2.reset(88888);

		cout << endl;

		cout << bs2.test(10) << endl;
		cout << bs2.test(4599) << endl;
		cout << bs2.test(99) << endl;
		cout << bs2.test(100) << endl;
		cout << bs2.test(101) << endl;
		cout << bs2.test(88888) << endl;
	}

	template <size_t N>
	class twobitset
	{
	public:
		twobitset()//初始化列表会初始化
		{}

		void set(size_t x)
		{
			if (!_bs1.test(x) && !_bs2.test(x))
			{
				//出现0次，则搞成01
				_bs2.set(x);
			}
			else if (!_bs1.test(x) && _bs2.test(x))
			{
				//出现1次，则搞成10
				_bs1.set(x);
				_bs2.reset(x);
			}

			//10出现1次以上，不需要变他
		}
		void PrintOnce()
		{
			for (size_t i = 0; i < N; i++)
			{
				if (!_bs1.test(i) && _bs2.test(i))
				{
					//如果是01，说明出现一次，可以打印出来
					cout << i << " ";
				}
			}
		}

	private:
		bitset<N> _bs1;//用的是我们自己写的bitset，编译器优先在wyn命名空间找
		bitset<N> _bs2;
	};

	void test_twobitset1()
	{
		qian::twobitset<100> tbs;
		int arr[] = { 3,5,3,99,99,67,45,51,52,52 };
		cout << "出现一次的字符为：";
		for (auto e : arr)
		{
			tbs.set(e);
		}
		tbs.PrintOnce();
		cout << endl;
	}


	// 模拟位图找交集
	void test_interbitset()
	{
		int a1[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };
		int a2[] = { 5,3,5,99,6,99,33,66 };
		bitset<100> bs1;
		bitset<100> bs2;
		for (auto e : a1)
		{
			bs1.set(e);
		}
		for (auto e : a2)
		{
			bs2.set(e);
		}
		cout << "交集为：" ;
		for (size_t i = 0; i < 100; i++)
		{
			if (bs1.test(i) && bs2.test(i))
			{
				cout << i << " " ;
			}
		}
	}



}

